\section{Pattern matching in Scala}

\subsection{The Scala language}

To quote its creators:

\begin{quote} 
Scala is a general purpose programming language designed to express common
programming patterns in a concise, elegant, and type-safe way. It smoothly
integrates features of object-oriented and functional languages.\cite{Scala}
\end{quote}

The Scala compiler is called \texttt{scalac} and will occasionnaly be refered
to as such.

The goal of this report is not to extensively describe Scala, as an exhaustive
literature exist to fulfill this need.\footnotemark Our purpose here is simply to
provide the knowledge required to understand all examples in this report. 

We will now go through the relevant aspects of pattern matching in Scala.

\footnotetext{\cite{ScalaRef} for instance, gives a good overview of the language.}

\subsection{Pattern matching expressions}\label{scala_pattern_matching}

Let's start with a first, introductory, example: 

\begin{lstlisting}[caption={a first example},label={first_example}]
abstract class Tree
case class Node(l: Tree, v: Int, r: Tree) extends Tree
case object EmptyTree extends Tree

t match {
    case Node(l: Node,v,_) $\Rightarrow body_1$
    case Node(_,v,r: Node) if (v > 0) $\Rightarrow body_2$
    case n: Node $\Rightarrow body_3$
    case EmptyTree $\Rightarrow body_4$
}
\end{lstlisting}

The code above shows many of the aspects concerning the use of patterns in
Scala. 

First of all, we can observe that the class hierarchy is a classical algebraic
data type definition. The \textbf{case} keyword is used to state this fact. The
\textbf{object} keyword, used before the declaration of the \textsf{EmptyTree}
class, declares that it is a singleton.

The match expression, including the block of patterns, is how a pattern
matching expression looks like in Scala. Patterns are tested against the
selector -- in this case, \texttt{t} -- sequentially. As soon as a pattern matches its
shape, the whole expression evaluates to what is on its right-hand side, which
can be any valid Scala expression (represented by the metavariables $body_i$s
in our example). If no match is found, a \textsf{MatchError} exception
is thrown. 

\subsubsection{Different shapes of patterns}

Scala provides its users with quite an extended range of ways to define
patterns. In order to get acquainted with the syntax, we informally describe,
by showing some examples, the general structures used to construct patterns:

\begin{itemize}

	\item[] \textbf{case} \_ $\Rightarrow \ldots$ : is a \emph{wildcard}. As
	its name suggest, it declares a pattern that match on any component. 
	
	\item[] \textbf{case} EmptyTree $\Rightarrow \ldots$ : matching an object
	is straightforward.
	
	\item[] \textbf{case} Node(\_,v,\_) $\Rightarrow \ldots$ : first, the
	variable $v$ is bound to the corresponding component of the \textsf{Node} class. We
	observe that \emph{wildcard}s can also be used in place of the constructor
	arguments.
	
	\item[] \textbf{case} Node(left: Node,v,\_) $\Rightarrow \ldots$ : type
	restrictions can be inserted in the pattern. The pattern matches the
	\emph{selector} if and only if it is a $Node$ whose left branch is also a
	$Node$. 
	
	\item[] \textbf{case} Node(Node(\_,5,\_),\_,\_) $\Rightarrow \ldots$ :
	considering the recursive nature of algebraic data type, it is not hard to
	guess that we are allowed to define complex patterns. The pattern matches
	the \emph{selector} if and only if it is a $Node$ whose left branch is a
	$Node$ with value $5$. 
	
	\item[] \textbf{case} Node(left,v,right) \textbf{if} (v $>$ 0) $\Rightarrow
	\ldots$ : the variable bound in the pattern can be immediately used in the
	guard to express conditions. The pattern is executed if and only if the
	\emph{selector} is a $Node$ whose value $v$ is greater than $0$.

\end{itemize}

These are the basic pattern constructions that should be kept in mind to read
the rest of this report. By now, the previous example should be perfectly
clear. 

\subsubsection{Matching primitive types}

In Scala, pattern matching can also be used on primitive types ($Int$, $Float$,
$Double$ and $Boolean$). The behaviour is then, as one would expect, similar to
a standard \textbf{switch} expression. Consider the following simple example:

\begin{lstlisting}[caption={pattern matching on integers}]
t: Int match {
    case 0 $\Rightarrow body_1$
    case v if (v != 0 && v % 2 == 0) $\Rightarrow body_2$
    case v if (v != 0 && v % 2 == 1) $\Rightarrow body_3$
}
\end{lstlisting}

\subsection{What can be checked in Scala}\label{what_can_be_checked_in_Scala}

\texttt{scalac} is able to check a limited set of properties on pattern
matching expressions. For instance, it is able to detect unreachable patterns
to some extent.\footnote{It becomes less accurate once you use guards.} For
example:

\begin{lstlisting}[caption={unreachable pattern}]
t match {
    case Node(_,_,_) $\Rightarrow body_1$
    case Node(_,0,_) $\Rightarrow body_2$
    case EmptyTree $\Rightarrow body_3$
}
\end{lstlisting}

The second pattern can never be reached. An attempt to compile the example will
fail, as the compiler will exit with an \emph{unreachable code} error message. 

Pattern matching expressions can be checked for completeness if the selector is
an instance of a \textbf{sealed} class. To quote the Scala reference:
\begin{quote}
A \textbf{sealed} class may not be directly inherited, except if the inheriting
template is defined in the same source file as the inherited class.
\cite{ScalaRef}
\end{quote}
The consequence of this restriction is that all subclasses are available at
compile time, and thus the hierarchy cannot be further extended. This is an
important requirement to show completeness, as it guarantees that the complete
set of types can be statically determined.
		
To enable the completeness check, Example~\ref{first_example} would be
rewritten as follows:

\begin{lstlisting}[caption={sealed class}]
sealed abstract class Tree
case class Node(l: Tree, v: Int, r: Tree) extends Tree
case object EmptyTree extends Tree
\end{lstlisting}

Completeness on \textbf{sealed} classes is checked correctly, except when
dealing with guards. If a guard is used to refine a pattern, then the
\texttt{scalac} will assume that the expression is not complete unless the same
pattern is declared without the guard. The following example would be correctly
checked: 

\begin{lstlisting}[caption={completeness on sealed classes}]
t match {
    case Node(_,v,_) $\Rightarrow body_1$
    case EmptyTree $\Rightarrow body_2$
}
\end{lstlisting}

On the other hand, Example~\ref{scala_and_guards} would generate a \emph{match is not exhaustive!} message. 

\begin{lstlisting}[caption={completeness checks fail with guards},label={scala_and_guards}]
t match {
    case Node(_,v,_) if (v == 0) $\Rightarrow body_1$
    case Node(_,v,_) if (v != 0) $\Rightarrow body_2$
    case EmptyTree => $body_n$
}
\end{lstlisting}

To get rid of the warning message, the programmer is left with only three choices:
\begin{enumerate}
\item Rewrite its pattern matching expression without guards
\item Rewrite its pattern matching expression in such a way that every pattern with a guard has is also present without it
\item Use the \textsf{@unchecked} annotation on the selector to disable the warning, as shown in the next example
\end{enumerate}

\begin{lstlisting}[caption={disabling the warning}]
(t:@unchecked) match {
	case Node(_,v,_) if (v == 0) $\Rightarrow body_1$
	case Node(_,v,_) if (v != 0) $\Rightarrow body_2$
	case EmptyTree  $\Rightarrow body_n$
}
\end{lstlisting}

Of course, none of the above solutions are satisfactory; in the first two
cases, the programmer had to rewrite its expression -- probably in a less
natural way than initially -- to meet the needs of the compiler. In the last
case, he simply disabled the warning, which means other errors could go
unnoticed.

This completes the overview of the implementation of completeness check in
Scala. Nothing has to be said about disjointness, as it is simply not
checkable.

\subsection{Object-oriented pattern matching}
So far, we have only talked about pattern matching on case classes. However,
Scala has recently seen the introduction of an additional construct to allow
for pattern matching on arbitrary classes, namely \emph{extractors}.

Any class which correctly implements the \texttt{apply} and \texttt{unapply}
methods can now be matched on. Of course, this subject is definitely more
complex than what we have just described, and it involves concepts that go way
beyond the scope of this work. The current reference about Scala extractors is
\cite{ScalaExtractors}.

\subsection{Syntactic sugar for lists}

Scala, as a functional language working extensively with lists has a dedicated syntax for them:

\begin{lstlisting}
z match {
    case Nil $\Rightarrow \ldots$
    case x :: xs $\Rightarrow \ldots$
}
\end{lstlisting}

However, this notation is simply syntactic sugar for the following class hierarchy:\footnotemark

\begin{lstlisting}
sealed abstract class List[B]
case final class ::[B](hd: B, tl: List[B]) extends List[B]
case object Nil extends List[Nothing]
\end{lstlisting}

\footnotetext{Note that $B$ in this example is a parametric type and $Nothing$ is Scala's bottom type.}
